#include <stdio.h>
#include <stdlib.h>

typedef char VertexType;			/* 顶点类型由用户定义 */
typedef int  EdgeType;				/* 边上的权值类型应由用户定义 */
#define MAXVEX 9					/* 最大顶点数，应由用户定义 */
#define INFINITY 65535				/* 用65535来代表∞ */

typedef struct
{
	VertexType vexs[MAXVEX];		/* 顶点表 */
	EdgeType arc[MAXVEX][MAXVEX];	/* 邻接矩阵，可看做边表 */
	int numVertexes, numEdges;		/* 图中当前的顶点数和边数 */
}MGraph;

void CreateMGraph(MGraph *G, VertexType vertex[MAXVEX], EdgeType edge[MAXVEX][MAXVEX])
{
    int i,j;
    for(i=0;i < MAXVEX; i++)
    {
        G->vexs[i] = vertex[i];
        for(j=0; j < MAXVEX; j++)
        {
            G->arc[i][j] = edge[i][j];
        }
    }
    G->numEdges = 15;
    G->numVertexes = 9;
}



/* Prim 算法生成最小生成树*/
void MiniSpanTree_Prim(MGraph G)
{
	int min, i, j, k;
	int adjvex[MAXVEX]; /* 保存相关顶点下标 */
	int lowcost[MAXVEX];/* 保存相关顶点间边的权值 */
	lowcost[0] = 0;		/* 初始化第一个权值为0，即v0加入生成树 */
			/* lowcost 的值为0，在这里就是此下标的顶点已经加入生成树 */
	adjvex[0] = 0; 		/* 初始化第一个顶点下标为0 */
	for (i = 1; i < G.numVertexes; ++i)
	{
		lowcost[i] = G.arc[0][i];
		adjvex[i] = 0;
	}
	for (i = 1; i < G.numVertexes; ++i)
	{
		min = INFINITY;

		j = 1;
		k = 0;
		while(j < G.numVertexes)
		{
			if (lowcost[j] != 0 && lowcost[j] < min)
			{
				min = lowcost[j];
				k = j;
			}
			j++;
		}
		printf("(%d,%d)\n", adjvex[k], k);
		lowcost[k] = 0;
		for (j = 1; j < G.numVertexes; ++j)
		{
			if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
			{
				lowcost[j] = G.arc[k][j];
				adjvex[j] = k;
			}
		}
	}
}

int main()
{
    VertexType vertex[MAXVEX] = {'0','1','2','3','4','5','6','7','8'};
    EdgeType edge[MAXVEX][MAXVEX] =
    {
        {0, 10, INFINITY, INFINITY, INFINITY, 11, INFINITY, INFINITY, INFINITY},
        {10, 0, 18, INFINITY, INFINITY, INFINITY, 16, INFINITY, 12},
        {INFINITY, INFINITY, 0, 22, INFINITY, INFINITY, INFINITY, INFINITY, 8},
        {INFINITY, INFINITY, 22, 0, 20, INFINITY, INFINITY, 16, 21},
        {INFINITY, INFINITY, INFINITY, 20, 0, 26, INFINITY, 7, INFINITY},
        {11, INFINITY, INFINITY, INFINITY, 26, 0, 17, INFINITY, INFINITY},
        {INFINITY, 16, INFINITY, INFINITY, INFINITY, 17, 0, 19, INFINITY},
        {INFINITY, INFINITY, INFINITY, 16, 7, INFINITY, 19, 0, INFINITY},
        {INFINITY, 12, 8, 21, INFINITY, INFINITY, INFINITY, INFINITY, 0}
    };
    MGraph G;
    CreateMGraph(&G, vertex, edge);

    MiniSpanTree_Prim(G);

    return 0;
}










